Lambda the Ultimate

I am sad to note that Jean Ichbiah, the lead designer of Ada, passed away on January 26, 2007.

Ada83, the reference manual for which appeared in 1983, is commonly known as the first version of Ada. Prior to that, in 1977, four contractors were picked to produce prototype languages, matching the requirements of the Ironman document (which led the way to the final Ada requirements specification, the Steelman). The prototypes were named green, red, blue and yellow. The green language, proposed by a team at Cii Honeywell Bull led by Jean D. Ichbiah, was chosen and led the way to Ada83. See here for more detailed timeline of the history of Ada.

While the design of Ada83 and Ada95 were both team efforts, in both cases the design was guided by a team leader whose vision and aesthetics regarding programming languages shaped the language. All versions of Ada owe much to Jean Ichbiah who shaped the core of the language used today.

Meta-Compilation of Language Abstractions, a dissertation by Pinku Surana.

High-level programming languages are currently transformed into efficient low-level code using optimizations that are encoded directly into the compiler. Libraries, which are semantically rich user-level abstractions, are largely ignored by the compiler. Consequently, library writers often provide a complex, low-level interface to which programmers "manually compile" their high-level ideas. If library writers provide a high-level interface, it generally comes at the cost of performance. Ideally, library writers should provide a high-level interface and a means to compile it efficiently.

This dissertation demonstrates that a compiler can be dynamically extended to support user-level abstractions. The Sausage meta-compilation system is an extensible source-to-source compiler for a subset of the Scheme programming language. Since the source language lacks nearly all the abstractions found in popular languages, new abstractions are implemented by a library and a compiler extension. In fact, Sausage implements all its general-purpose optimizations for functional languages as compiler extensions. A meta-compiler, therefore, is merely a shell that coordinates the execution of many external extensions to compile a single module. Sausage demonstrates that a compiler designed to be extended can evolve and adapt to new domains without a loss of efficiency.

A very interesting and detailed paper, which touches on many perennial LtU subjects, and once again shifts the line between user programs and the compiler. If you're tempted to say "this sounds like X...", then read Chapter 2, which gives a comprehensive comparison to alternative approaches, including static type inference, traditional macro systems, templates, partial evaluation, and multi-stage languages such as MetaML and MetaOCaml.

Some carefully selected quotes which I think summarize the summary quite well:

The Sausage system provides a framework for programmers to write new domain-specific optimizations and inject them into the main compiler.
...
This dissertation takes the rather extreme view that anything beyond Core Scheme is a compiler extension.

Pinku Surana will be presenting this work at a meeting of LispNYC on Feb 13th in New York City. An announcement with details of the meeting can be found here.

On Decidability of Nominal Subtyping with Variance. Andrew J. Kennedy, Benjamin C. Pierce. FOOL'07. January 2007

We investigate the algorithmics of subtyping in the presence of nominal inheritance and variance for generic types, as found in Java 5, Scala 2.0, and the .NET 2.0 Intermediate Language. We prove that the general problem is undecidable and characterize three different decidable fragments. From the latter, we conjecture that undecidability critically depends on the combination of three features that are not found together in any of these languages: contravariant type constructors, class hierarchies in which the set of types reachable from a given type by inheritance and decomposition is not always finite, and class hierarchies in which a type may have multiple supertypes with the same head constructor. These results settle one case of practical interest: subtyping between ground types in the .NET intermediate language is decidable; we conjecture that our proof can also be extended to show full decidability of subtyping in .NET. For Java and Scala, the decidability questions remain open; however, the proofs of our preliminary results introduce a number of novel techniques that we hope may be useful in further attacks on these questions.

The undecidability of subtyping is proved by reduction from the Post Correspondence Problem. Section 5 presents several decidable fragments.

Hot stuff!

Ralf Hinze and Andres Löh. Generic Programming, Now!. In Roland Backhouse, Jeremy Gibbons, Ralf Hinze and Johan Jeuring, editors, Spring School on Generic Programming, Lecture Notes in Computer Science. Springer-Verlag, 2006.

Tired of writing boilerplate code? Tired of repeating essentially the same function definition for lots of different data types? Datatype-generic programming promises to end these coding nightmares. In these lecture notes, we present the key abstractions of datatype-generic programming, give several applications, and provide an elegant embedding of generic programming into Haskell. The embedding builds on recent advances in type theory: generalised algebraic data types and open data types. We hope to convince you that generic programming is useful and that you can use generic programming techniques today!

Yes, more functional generic programming...

Open data types and open functions are discussed here, but I think this paper wasn't featured on the homepage before.

First Class Relationships in an Object-oriented Language, by Gavin Bierman and Alisdair Wren, was a paper published at ECOOP 2005.

They show how to add relationships as a first-class mechanism to a Java-like language, where by relationships in something like the UML sense. Cribbing from their examples, you might have a Student class and a Course class, and an Attends relationship, which is a binary relation between Students and Courses. Then, there are mechanisms to dynamically add and remove entries from a relationship, and to query a relationship about whether particular objects are in them or not.

Now my personal random editorialisation: I think this is a really interesting idea, because these kinds of things pops up all the time in OO models, and having relations be first class means that you can move some state out of individual object instances, which is always a good thing, and the type system can guarantee something about what relationships will hold. The things that scare me about this idea are first, that you can potentially add a lot of heap pressure by keeping objects live longer, and second, that you now have much more pervasive aliasing of objects in your program. I don't know if these are real problems though, and anyway the feature is cool enough that I'd be interested in programming in a language with support for it, just to see what it's like.

Dear all,

the proceedings of PLAN-X 2007, the Fifth ACM SIGPLAN Workshop on
Programming Language Technologies for XML (held on January 20, 2007 in Nice, France, collocated with and just after POPL 2007) have been posted and are available for download (PDF): www.plan-x-2007.org

The 100-page volume contains eight research papers and four software demonstration descriptions. There should be something in there for everybody (who hangs out here, that is).

Enjoy,
—Torsten Grust (PLAN-X 2007 General Chair)

I thought this paper was one of the most interesting papers at POPL this year. In it, Malacaria uses information theory to provide a quantitative analysis of how much high-security information is revealed to an attacker by a particular program.

This is extremely interesting work, because without a framework like this I don't think information flow analysis can be used to analyze real programs for security holes. That's because to date it has been all-or-nothing: the analysis flags a warning if any information is leaked to an attacker, and this is much too restrictive a notion. For example, a password routine "leaks information" to an attacker, because if an attacker guesses a password and is blocked, they've learned that the random string they guessed is not the password. But as long as an attacker can't do a brute-force search, the program is actually secure, even though it technically leaks information.

However, in Malacaria's approach, you can make this idea of security more precise, by saying something like "a secure program leaks at most c bits of information", and this makes sense because there's a quantitative measure of information leakage.

Very cool!

40 years after the invention of OO, I am ready to appreciate objects quite a bit because I can use them in combination with functional programming. Naturally, I call this mix functional OO programming. (I don’t quite count functional objects in C++ or ‘functors’ in Java, a misnomer BTW, as functional programming.)

Ralf lists several of his papers that apply the notion of functional OO programming. He also shares his wish list for future versions of C#.

Programming the Greedy CAM Machine. Erik Ruf. January 2007

The Greedy CAM architecture describes a class of experimental processors that aim to cope with memory latency and enable parallelism by combining a streams-and-kernels execution model with a relational-query-based memory model. This article focuses on the programming abstraction (equivalent to the ISA in more conventional systems) of Greedy CAM systems, as exemplified by a low-level intermediate language. Using a series of small example programs, we demonstrate several programming idioms and analyze their performance using a simple functional-level simulator. We also suggest extensions needed for the implementation of higher-level programming abstractions.

Section 6.8 is on the suitability of LINT, the low-level intermediate language described in the paper, as a target language for the compilation of higher-level abstractions. But comments on the general issues discussed in the paper are welcome as well...

R.W. Floyd's Turing Award Lecture “The Paradigms of Programming” is freely available in an online journal here. It is almost 30 years old, and still very much relevant. A quotation: To the designer of programming languages, I say: unless you can support the paradigms I use when I program, or at least support my extending your language into one that does support my programming methods, I don’t need your shiny new languages [...]